// 顺序搜索 / 线性搜索

const DO_NOT_EXIST = -1;
function sequentialSearch(arr, value, equalFn = defaultEquals) {
    for (let i = 0; i < arr.length; i++) {
        if (equalFn(value, arr[i])) {
            return i;
        }
    }
    return DO_NOT_EXIST;
}

// 二分搜索
// 1. 选择数组的中间值
// 2. 如果选中值是待搜索值，执行完成
// 3. 如果待搜索比选中小，返回1并在选中值的左边去找
// 4. 如果待搜索比选中大，返回1并在选中值右边去找

function binarySearch(array, value, compareFn = defaultEquals) {
    const sortedArray = quickSort(array);
    let low = 0;
    let high = sortedArray.length - 1;
    while (lesserorEquals(low, high, compareFn)) {
        const mid = Math.floor((low + high) / 2);
        const element = sortedArray[mid];
        if (compareFn(element, value) === Compare.LESS_THAN) {
            low = mid + 1;
        } else if (compareFn(element, value) === Compare.BIGGER_THAN) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return DO_NOT_EXIST;
}

function lesserorEquals(a, b, compareFn) {
    const comp = compareFn(a, b);
    return comp === Compare.LESS_THAN || Compare.BIGGER_THAN;
}

// 内插搜索 - 已排序的数组
// 1. 使用position公式选中一个值
// 2. 如果选中值是待搜索值，执行完成
// 3. 如果待搜索比选中小，返回1并在选中值的左边去找
// 4. 如果待搜索比选中大，返回1并在选中值右边去找

function interpolationSearch(arr, value, compareFn = defaultCompare, equalsFn = defaultEquals, diffFn = defaultDiff) {
    const { length } = arr;
    let low = 0;
    let high = length - 1;
    let position = -1;
    let delta = -1;
    while (
        low <= high
        && biggerOrEquals(value, arr[low], compareFn)
        && lesserOrEquals(value, arr[high], compareFn)
    ) {
        delta = diffFn(value, arr[low]) / diffFn(arr[high], arr[low]); //
        position = low + Math.floor((high - low) / delta);
        if (equalsFn(arr[position], value)) {
            return position
        }
        if (compareFn(arr[position], value) === Compare.LESS_THAN) {
            low = position + 1;
        } else {
            high = position - 1;
        }
    }
    return DO_NOT_EXIST;
}

function biggerOrEquals(a, b, compareFn) {
    const comp = compareFn(a, b);
    return comp === Compare.BIGGER_THAN || comp === Compare.EQUALS;
}

function lesserOrEquals(a, b, compareFn) {
    const comp = compareFn(a, b);
    return comp === Compare.LESS_THAN || comp === Compare.EQUALS;
}

// 随机算法  Fisher-Yates随机
function shuffle(array) {
    for (let i = array.length - 1; i > 0; i--) {
        const randomIndex =  Math.floor(Math.random() * (i + 1));
        swap(array, i, randomIndex)
    }
    return array;
}